package cmlabs.numbertheoryutils.algorithms;

import cmlabs.generalutils.Pair;

import java.math.BigInteger;
import java.util.Collections;
import java.util.Vector;


public class DiscreteLogarithm {
    private static int lowerBound(Vector<Pair<Long>> a, long key) {
        int lo = -1;
        int hi = a.size();
        while (hi - lo > 1) {
            int mid = (lo + hi) / 2;
            long midVal = a.elementAt(mid).first;
            if (midVal < key) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return hi;
    }

    public static long findLogarithm(long a, long b, long m) {
        long msq = (long) Math.sqrt(m + .0) + 1;
        long msq2 = m / msq + (m % msq == 1 ? 1 : 0);
        Vector<Pair<Long>> values = new Vector<Pair<Long>>((int) msq2);
        for (int i = 1; i <= msq2; ++i) {
            values.add(new Pair<Long>(BigInteger.valueOf(a).modPow(BigInteger.valueOf(i * msq), BigInteger.valueOf(m)).longValue(), Long.valueOf(i)));
        }
        Collections.sort(values);
        for (int i = 0; i < msq; ++i) {
            long current = BigInteger.valueOf(a).modPow(BigInteger.valueOf(i), BigInteger.valueOf(m)).longValue();
            current = (current * b) % m;
            int index = lowerBound(values, current);
            if (index != values.size() && values.elementAt(index).first == current) {
                return values.elementAt(index).second * msq - i;
            }
        }
        return -1;
    }
}
